\documentclass{beamer}

%\usepackage{graphicx}
%\usepackage{tikz}
%\usepackage[absolute,overlay]{textpos}
%\usepackage{listings}
%\usepackage{textpos}

\usetheme{Antibes}
\usecolortheme[RGB={233,100,35}]{structure}

\usebackgroundtemplate{
    \includegraphics[width=370pt]{img/unict.jpg}
}

\newtheorem{samplecode}{Sample Code}

%\setbeamercovered{transparent}
\setbeamertemplate{footline}[frame number]{}

% Spaces
\newcommand{\N}{\vskip 0.3 cm}
\newcommand{\n}{\vskip 0.2 cm}
\newcommand{\TAB}{\hskip 4 cm}
\newcommand{\tab}{\hskip 0.6 cm}

% Colors
\newcommand{\red}[1]{\textcolor[rgb]{.8,0,0}{#1}}
\newcommand{\blue}[1]{\textcolor[rgb]{0,0,.7}{#1}}
\newcommand{\navy}[1]{\textcolor[rgb]{0,0,.5}{#1}}
\newcommand{\purple}[1]{\textcolor[rgb]{.7,0,.8}{#1}}
\newcommand{\green}[1]{\textcolor[rgb]{0,.6,.1}{#1}}


\title[A Distributed Graph Partitioning Algorithm]{
  A Distributed Graph Partitioning Algorithm 
 }%\subtitle[]{}
\author{Loris Fichera, Daniele Marletta}
\institute[Universit\`a di Catania]{
	Universit\`a degli Studi di Catania\\
        Corso di Laurea Specialistica in Ingegneria Informatica\\
        Corso di Sistemi Distribuiti
}
\date{September 7th, 2010}


\begin{document}

% Title Page
\begin{frame}[plain]
  \titlepage
\end{frame}
%

%
\section{Introduction}
\begin{frame}{Problem Statement}  
  \begin{itemize}
    \item
      Our work aims at implementing a \red{\emph{partitioning} algorithm} for
      undirected graphs
    \item
      The partitioning process identifies a number of sub-graphs, 
      according to a specific logic
    \item
      Analyzed graphs may meet the characteristics of a \emph{specific model}
  \end{itemize}
  \vfill
  \begin{small}
    In general, the graph partitioning problem is \red{NP-complete}.
  \end{small}
\end{frame}
%

%
\section{Graph models}
%
\begin{frame}{Graph Models}
Graphs are widely used to provide an effective representation of a set 
of actual \red{entities} and of their \red{inter-relations}. \\
Many graph models have been identified and described in mathematical terms.
Among them, we have:
\begin{itemize}
\item Random graphs
\item Small World models
\item Scale-Free models
\end{itemize}
\begin{figure}[!h]
  \begin{center}
    \fbox{\includegraphics[width=150pt]{img/graphs.png}}
  \end{center}
\end{figure}
\end{frame}
%
\begin{frame}{Random Graphs}
\begin{itemize}
\item \red{N} nodes, connected each other with probability \red{p}\\
\item \red{p}$*$\red{N}$*$(\red{N} - 1) / 2 connections
\item Average path length is $ L_{rand} \propto \ln\red{N} / connectivity$
\item \red{Degree of connectivity}\footnote{often addressed simply as \emph{degree}} 
  follows the \emph{Poisson distribution}
\begin{figure}[!h]
  \begin{center}
    \fbox{\includegraphics[width=70pt]{img/random_graph.png}}
  \end{center}
\end{figure}
\end{itemize}
\end{frame}
%
\begin{frame}{The Watts-Strogatz `Small World' model}
\begin{itemize}
\item \red{N} nodes, arranged in a ring, each of which is connected with 
some of its neighbours
\item Existing connections are then \purple{rewired} with probability \red{p}
\item Average path length decreases for higher values of \red{p}

\item \red{Degree} distribution ranges from the \emph{delta Dirac 
  function} ($\red{p} = 0$) to a \emph{Poisson} distribution ($\red{p} = 1$)
\end{itemize}
\begin{figure}[!h]
  \begin{center}
    \fbox{\includegraphics[width=70pt]{img/small_world_model.png}}
  \end{center}
\end{figure}
\end{frame}
%
\begin{frame}{The Barabasi-Albert `scale-free' model}
The algorithm to generate a BA graph is made of two steps:
\begin{itemize}
  \item \textbf{Growth:} start with a small number of nodes ($m_0$);
    at every time step, a new node is introduced and connected to 
    $ m \le m_0$ already existing nodes
  \item \textbf{Preferential Attachment:} the probability $p_i$ that a new node 
    will be connected to the already existing node \emph{i} which has already $k_i$ 
    connections is $p_i = \frac{k_i}{\sum_{j}k_j}$
\end{itemize}
\begin{figure}[!h]
  \begin{center}
    \fbox{\includegraphics[width=70pt]{img/scale_free_model.png}}
  \end{center}
\end{figure}
\begin{itemize}
\item \red{Degree} follows a \emph{Power-Law} distribution
\end{itemize}
\end{frame}
%
\begin{frame}{Graph Generation}
We used the \red{peersim} 
library\footnote{\tiny{http://peersim.sourceforge.net/}} to generate the graphs.
\begin{samplecode}
  \begin{small}
  // Generate a graph with an average of \red{k} connections\newline
  // per node and randomness \red{r}\newline
  Graph g = GraphFactory.wireKOut(g, k, r);\newline

  // Generate a WS graph starting with initial \red{k} connections\newline
  // per node, a rewiring probability \red{p} and randomness \red{r}\newline
  Graph g = GraphFactory.wireWS(g, k, p, r);\newline

  // Generate a BA graph starting from \red{k} initial nodes\newline
  // and randomness \red{r}\newline
  Graph g = GraphFactory.wireScaleFreeBA(g, k, r);\newline
  \end{small}
\end{samplecode}
\end{frame}
%

%
\section{The Partitioning Algorithm}
%
\begin{frame}{Class Diagram}

  \begin{figure}[!h]
    \begin{center}
      \fbox{\includegraphics[scale=0.3]{img/classDia.png}}
    \end{center}
  \end{figure}
 
\end{frame}
%
\begin{frame}{Architecture}
\begin{itemize}
\item Some steps of the algorithm have been implemented as 
  Web Services methods
\item The WS have been deployed on a 
  \red{Glassfish}\footnote{http://glassfish.dev.java.net/} server
\end{itemize}
\begin{samplecode}
  \begin{tiny}
    \begin{tabbing}
      @WebService() \= public class \red{GraphService} \{\\
      \> @WebMethod() public int [] \red{countNeighbours} (@WebParam() int [] adjVector) \{...\}\\
      \> @WebMethod() public String [] \red{processConnections} (@WebParam() int [] neighboursCount) \{ ... \}\\
      \> @WebMethod() \= public int [] \red{computeHops} ( @WebParam() int [] adjVector, \\
      \> \> @WebParam() int [] neighbourCount,\\
      \> \> @WebParam() int hyperNodeIndex) \{ ... \}\\
      \}
    \end{tabbing}
  \end{tiny}
\end{samplecode}
\end{frame}
%
\begin{frame}{WS Methods}
  
  \begin{itemize}
    \item The \red{countNeighbours()} method receives as input the graph generated using one of the
    above-mentioned models, and identifies, for each node, the number of its neighbours.
    \item The \red{processConnections()} method classifies the nodes in 5 categories, depending on the 
    number of neighbours: IC, MC, C, PC, SC. IC contains the hyper-connected nodes.
    \item The \red{computeHops()} method determines the distance of all nodes from a given IC node by
    using an \purple{Uniform-Cost Search} algorithm to traverse the graph.
  \end{itemize}
  
\end{frame}
%
\begin{frame}{Distributing the Computation}
  
  \begin{itemize}
    \item The computation of distances can proceed in parallel and independently for each IC node.
    \item After collecting the result of all \emph{computeHops()} invocations, the client execute the
    \purple{partitioning} algorithm by assigning every node to the class of the \purple{nearest} IC.
    
    \n
    \item Whenever a node has the same distance from two or more IC nodes, we have a \purple{conflict}
    between the corresponding classes.
    \item To obtain a fair classification, the conflict must be solved by assigning the node to the class
    which has currently less members.
  \end{itemize}
  
\end{frame}
%
\begin{frame}{Class Conflicts}
  We distinguish the following scenarios:
  \begin{enumerate}
    \item If \red{all} competing classes has zero members, the node is randomly assigned.
    \item If \red{some} competing classes has zero members, the node is randomly assigned to one of these classes.
    \item If \red{none} competing class has zero members, the classes are ordered in \purple{ranks} depending on
    the number of their members. Then:
    \begin{itemize}
        \item A temporary rank \emph{$tr_i$} is selected using \emph{preferential attachment}.
        \item The winner rank is: \emph{$wr = numRanks-tr_i$}. Thus, the smaller class will be selected with higher
        probability.
        \item If the winner rank has two or more classes, the node is randomly assigned to one of these classes.
    \end{itemize}
  \end{enumerate}
  
\end{frame}
%

%
\section{Sample Outputs}
%
\subsection{Random Graph - 30 nodes - randomness=50\%}
\begin{frame}{}
  \begin{figure}[!h]
    \begin{center}
      \fbox{\includegraphics[scale=0.22]{img/r-100-05.png}}
    \end{center}
  \end{figure}
\end{frame}
%
\subsection{Watts-Strogatz Graph - 100 nodes - initial connections=2\% - randomness=10\%}
\begin{frame}{}
  \begin{figure}[!h]
    \begin{center}
      \fbox{\includegraphics[scale=0.25]{img/ws-100-2-01.png}}
    \end{center}
  \end{figure}
 
\end{frame}
%
\subsection{Watts-Strogatz Graph - 100 nodes - initial connections=4\% - randomness=10\%}
\begin{frame}{}
  \begin{figure}[!h]
    \begin{center}
      \fbox{\includegraphics[scale=0.3]{img/ws-100-4-01.png}}
    \end{center}
  \end{figure}
 
\end{frame}
%
\subsection{Watts-Strogatz Graph - 100 nodes - initial connections=5\% - randomness=20\%}
\begin{frame}{}
  \begin{figure}[!h]
    \begin{center}
      \fbox{\includegraphics[scale=0.3]{img/ws-100-5-02.png}}
    \end{center}
  \end{figure}
 
\end{frame}
%
\subsection{Barabasi-Albert Graph - 100 nodes - initial connections=2\% - randomness=50\%}
\begin{frame}{}
  \begin{figure}[!h]
    \begin{center}
      \fbox{\includegraphics[scale=0.3]{img/ba-100-2-05.png}}
    \end{center}
  \end{figure}
 
\end{frame}
%
\subsection{Barabasi-Albert Graph - 100 nodes - initial connections=8\% - randomness=50\%}
\begin{frame}{}
  \begin{figure}[!h]
    \begin{center}
      \fbox{\includegraphics[scale=0.3]{img/ba-100-8-05.png}}
    \end{center}
  \end{figure}
 
\end{frame}
\end{document}
